/*
 * Copyright (C), 2015-2018
 * FileName: Solution100
 * Author:   zhao
 * Date:     2018/9/7 18:08
 * Description: 100. 相同的树
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredone;

import com.lizhaoblog.diynode.TreeNode;

/**
 * 〈一句话功能简述〉<br>
 * 〈100. 相同的树〉
 *
 * @author zhao
 * @date 2018/9/7 18:08
 * @since 1.0.1
 */
public class Solution100 {
  /**************************************
   * 题目
   给定两个二叉树，编写一个函数来检验它们是否相同。

   如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

   示例 1:

   输入:       1         1
   / \       / \
   2   3     2   3

   [1,2,3],   [1,2,3]

   输出: true
   示例 2:

   输入:      1          1
   /           \
   2             2

   [1,2],     [1,null,2]

   输出: false
   示例 3:

   输入:       1         1
   / \       / \
   2   1     1   2

   [1,2,1],   [1,1,2]

   输出: false

   **************************************/

  /**************************************
   *
   * 想法：
   *    递归遍历左右节点，判断值是否相同
   * 我的做法
   *    超过92.18%的测试案例
   * 总结：
   *    使用if-else的结构速度会比if--if--if的速度快
   * ***********************************/
  public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
      return true;
    }
    if (p == null) {
      return false;
    }

    if (q == null) {
      return false;
    }

    if (p.val != q.val) {
      return false;
    }

    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
  }

  /**************************************
   * 比我好的答案
   * ***********************************/
  public boolean better(TreeNode p, TreeNode q) {
    if (q == null && p == null) {
      return true;
    } else if (q == null) {
      return false;
    } else if (p == null) {
      return false;
    }
    if (p.val == q.val) {
      return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    return false;

  }

}
